package com.hanxiaozhang.recursion.violentrecursion;

/**
 * 〈一句话功能简述〉<br>
 * 〈在 N * N 的棋盘上要摆 N 个皇后，要求任何两个皇后不同行、不同列，
 *   也不在同一条斜线上给定一个整数 n，返回 n 皇后的摆法有多少种。
 *   n=1，返回1；n=2 或3，2皇后和3皇后问题无论怎么摆都不行，返回0 ；
 *   n=8，返回92。〉
 *
 * @author hanxinghua
 * @create 2021/10/19
 * @since 1.0.0
 */
public class NQueens {


    public static void main(String[] args) {
        int n = 14;

        long start = System.currentTimeMillis();
        System.out.println(num2(n));
        long end = System.currentTimeMillis();
        System.out.println("cost time: " + (end - start) + "ms");

        start = System.currentTimeMillis();
        System.out.println(num1(n));
        end = System.currentTimeMillis();
        System.out.println("cost time: " + (end - start) + "ms");

    }


    public static int num1(int n) {
        if (n < 1) {
            return 0;
        }
        // record[i] -> i行的皇后，放在了第几列
        int[] record = new int[n];
        return process1(0, record, n);
    }


    /**
     * 前提：record[0..i-1]的皇后，任何两个皇后一定都不共行、不共列，不共斜线
     * 目前来到了第i行。
     *
     * @param i 来到了第i行
     * @param record  record[0..i-1]表示之前的行，放了的皇后位置
     * @param n  n代表整体一共有多少行
     * @return  返回值是，摆完所有的皇后，合理的摆法有多少种
     */
    public static int process1(int i, int[] record, int n) {
        // 来到终止行，证明此种摆法成立，返回1情况
        if (i == n) {
            return 1;
        }
        // 没到终止行，还有皇后要摆
        // 结果数
        int res = 0;
        // 当前行在i行，尝试i行所有的列  -> j
        for (int j = 0; j < n; j++) {
            // 判断是否有效
            if (isValid(record, i, j)) {
                // 有效记录位置
                record[i] = j;
                // 有效遍历下一行情况
                res += process1(i + 1, record, n);
            }
        }
        return res;
    }

    /**
     *  当前i行的皇后，放在j列，会不会和之前(0..i-1)的皇后，不共行共列或者共斜线，
     *  如果是，认为有效;如果不是，认为无效
     *
     * @param record
     * @param i 行
     * @param j 列
     * @return
     */
    public static boolean isValid(int[] record, int i, int j) {
        // 之前的某个k行的皇后
        for (int k = 0; k < i; k++) {
            // j == record[k]  说明不共列
            // Math.abs(record[k] - j) == Math.abs(i - k)  说明不斜线 ==> 对角线是  |行1 -列1| == |行2 -列2 |
            //  Math.abs() 绝对值
            if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {
                return false;
            }
        }
        return true;
    }


    /**
     * 请不要超过32皇后问题 ==> 优化常数项时间
     *
     * @param n
     * @return
     */
    public static int num2(int n) {
        if (n < 1 || n > 32) {
            return 0;
        }
        int limit = n == 32 ? -1 : (1 << n) - 1;
        return process2(limit, 0, 0, 0);
    }


    /**
     * 递归2
     *
     * @param limit 划定问题的规模
     * @param colLim 列的限制，1的位置不能放皇后，0的位置可以
     * @param leftDiaLim 左斜线的限制，1的位置不能放皇后，0的位置可以
     * @param rightDiaLim 右斜线的限制，1的位置不能放皇后，0的位置可以
     * @return
     */
    public static int process2(int limit,
                               int colLim,
                               int leftDiaLim,
                               int rightDiaLim) {
        // base case
        if (colLim == limit) {
            return 1;
        }
        // 所有候选皇后的位置，都在pos上
        //  colLim | leftDiaLim | rightDiaLim ==>总限制
        //  ~(colLim | leftDiaLim | rightDiaLim) ==> 左侧一坨0干扰，右侧每个1，可以尝试
        //  limit & (~(colLim | leftDiaLim | rightDiaLim)) ==> 左侧一坨1干扰，右侧每个0，可以尝试(limit与运算可以取反)
        int pos = limit & (~(colLim | leftDiaLim | rightDiaLim));
        int mostRightOne = 0;
        int res = 0;
        // 循环作用，每次都提取最右侧的1
        while (pos != 0) {
            // 提取出最右侧的1，剩下位置都是0
            mostRightOne = pos & (~pos + 1);
            pos = pos - mostRightOne;

            res += process2(limit,
                    // 原来列或上mostRightOne就是下一行列限制
                    colLim | mostRightOne,
                    // 原来列或上mostRightOne 然后左移1位
                    (leftDiaLim | mostRightOne) << 1,
                    // 原来列或上mostRightOne 然后无符号右移1位
                    (rightDiaLim | mostRightOne) >>> 1);
        }
        return res;
    }

}
